package panel.viewSpots.navigation
{
	import assists.ArrayUtils;
	
	public class PathChoose
	{
		private static var _nodeIndexList:Array = [];//记录景区中所有不重复的点
		private static var _roadInfoList:Array = [];//记录xml数据
		private static var _nodeList:Array = [];//记录整合好数据的所有结点数据
		private var _shortPath:Object = {};//记录每次寻路的最小路径及相关信息
		private var _addPath:Array = [];//记录添加的路线
		private var _removePath:Array = [];//记录删除掉路线
		private static var _normalPath:Array = [];//最终生成的路线
		private var _allTime:uint;//游览需要时间
		
		public function PathChoose()
		{
			
		}
		
		public function init(roadList:Array):void
		{
			_roadInfoList = roadList;
			//			1.将xml里的路线配置数据 转换成需要的数据类型
			generateNodeIndexList(_roadInfoList);
			generateNodeList();
			_normalPath = [
				seekNodeByIndex("0"),
				seekNodeByIndex("1"),
				seekNodeByIndex("2"),
				seekNodeByIndex("a"),
				seekNodeByIndex("7"),
				seekNodeByIndex("3"),
				seekNodeByIndex("6"),
				seekNodeByIndex("8")
			];
			_allTime = 65;
		}
		
		public function setStartIndex(startIndex:String):void
		{
			var isFind:Boolean;
			for(var i:int=0;i<_normalPath.length;i++)
			{
				if(_normalPath[i].index == startIndex)
				{
					isFind = true;
					_normalPath.splice(0,i);
					break;
				}
			}
			if(!isFind)
			{
				addPathNode(startIndex);
			}
			
		}
		
		private function commuteTime():void
		{
			var len:int = _roadInfoList.length;
			for(var i:int=0;i<len;i++)
			{
				if(_roadInfoList[i] == _roadInfoList[i + 1])
				{
					
				}
			}
		}
		/**
		 *获取添加点与路线中所有点的距离，然后比较，到最近点和最近点相邻点最近的点和原路返回的方式哪个更短 
		 * @param index
		 * 环线的情况 要考虑不用到上一景点，到上一个环线路口就行了
		 */		
		public function addPathNode(index:String):void
		{
			changeNodeVisit(index,true);
			//			找添加点到路线中所有点的距离
			var len:int = _normalPath.length;
			var allPathList:Array = [];
			var node:nodeStruct;
			for(var i:int=0;i<len;i++)
			{
				node = _normalPath[i];
				if(!node ||　node.nodeType == 1 || node.needVisit == false) continue;//去除掉路口 和不需要参观的景点   下一点必须是景点 上一点可以是路口
				if(_normalPath[i + 1] && node.index == _normalPath[i + 1].index)
				{
					continue;
				}
				startSeek(node.index,index);
				allPathList.push({cost:_shortPath.cost,path:_shortPath.path,index:node.index,pos:i});
			}
			
			//			比较添加点到前后两个点的最短距离
			var minCost:uint = 99999999;
			var minIndex:int;
			var allLen:int = allPathList.length;
			var pathType:int;//type为1 表示从该点出发 再从该店回来
			var minPathType:int = pathType;
			var minPathList:Array;//最小路径
			var isCircle:Boolean;
			for(i=0;i<allLen;i++)
			{
				if(i == 0 || i == allLen - 1)
				{
					if(minCost > allPathList[i].cost)
					{
						minCost = allPathList[i].cost;
						minIndex = i;
						pathType = 3;
					}
					continue;
				}else
				{
					if(ArrayUtils.checkInList(allPathList[i].path[0], allPathList[i + 1].path) || ArrayUtils.checkInList(allPathList[i + 1].path[0], allPathList[i].path))
					{
						continue;
					}else
					{
					isCircle = ArrayUtils.matchList(allPathList[i + 1].path, allPathList[i].path,"index");
					}
					if(isCircle)
					{
						allPathList[i].cost =  commuteCicleDistance(allPathList[i].path) + allPathList[i + 1].cost;
						pathType = 1;
					}else
					{
					allPathList[i].cost = allPathList[i].cost + allPathList[i + 1].cost;
						pathType = 2;
					}
					if(minCost > allPathList[i].cost || pathType == 2)
					{
						minCost = allPathList[i].cost;
						minIndex = i;
						minPathType = pathType;
						if(minPathType == 2) break;
					}
				}
				
			}
			
			//		获得添加位置 并添加到适当位置
			if(minPathType == 1)//往返路
			{
				_removePath = ArrayUtils.removeListByIndex(_normalPath,allPathList[minIndex].index,allPathList[minIndex + 1].index,"index");
				minPathList = allPathList[minIndex + 1].path;
				minPathList.push("");//通用会去掉后一数组的出发点 环线不需要
				_addPath = ArrayUtils.contackArrays(allPathList[minIndex].path,minPathList);
				ArrayUtils.instertListToArray(_addPath,_normalPath,allPathList[minIndex].pos);
				
			}else if(minPathType == 3)//在首位添加 
			{
				_removePath = ArrayUtils.removeListByIndex(_normalPath,allPathList[minIndex - 1].index,allPathList[minIndex].index,"index");
				_addPath = allPathList[minIndex].path;
				ArrayUtils.instertListToArray(_addPath,_normalPath,allPathList[minIndex].pos);
			}
			else
			{
				_removePath = ArrayUtils.removeListByIndex(_normalPath,allPathList[minIndex].index,allPathList[minIndex + 1].index,"index");
				_addPath = ArrayUtils.contackArrays(allPathList[minIndex].path,allPathList[minIndex + 1].path);
				ArrayUtils.instertListToArray(_addPath,_normalPath,allPathList[minIndex].pos);
			}
			
			ArrayUtils.printArray(_normalPath,"index");
		}
		
		public function removeSpot(spotIndex:String):void
		{
			changeNodeVisit(spotIndex,false);
			
			var removeInfo:Object = seekSpotInPath(spotIndex);
			if(removeInfo.pre == -1)
			{
				removeInfo.pre = 0;
				_removePath = _normalPath.splice(0,removeInfo.next);
				_removePath.push(_normalPath[removeInfo.next - 1]);
			}else if(removeInfo.next == -1)
			{
				removeInfo.next = _normalPath.length - 1;
				_removePath = _normalPath.splice(removeInfo.pre,_normalPath.length - removeInfo.pre);
				_removePath.unshift(_normalPath[removeInfo.pre]);
			}else
			{
				_removePath = _normalPath.splice(removeInfo.pre,removeInfo.next - removeInfo.pre + 1);
			startSeek(_removePath[0].index,_removePath[_removePath.length - 1].index);
			_addPath = _shortPath.path;
			ArrayUtils.instertListToArray(_addPath,_normalPath,removeInfo.pre);
			}

		}
		
		private function commuteCicleDistance(list:Array):uint
		{
			var endIndex:String;
//			1.找到连接到原路径上的第一个点
			for(var i:int=list.length - 1;i>0;--i)
			{
				for(var j:int=0;j<_normalPath.length;j++)
				{
					if(_normalPath[j].index == list[i].index)
					{
						endIndex = list[i].index;
						break;
					}
				}
				if(endIndex != null) break;
			}
//			2.计算两点之间的路线
			if(endIndex == null) return 999999;
			startSeek(list[list.length - 1].index,endIndex);
			return _shortPath.cost;
		}
		
		private function changeNodeVisit(spotIndex:String,isAdd:Boolean):void
		{
			_addPath = [];
			_removePath = [];
			var node:nodeStruct = seekNodeByIndex(spotIndex);
			node.needVisit = isAdd;
		}
		
		private function seekSpotInPath(spotIndex:String):Object
		{
			var startFind:Boolean;
			var nextSpotPos:int;
			var preSpotPos:int;
			
			for(var i:int=0;i<_normalPath.length;i++)
			{
				if(_normalPath[i].index == spotIndex)
				{
					startFind = true;
//					if(_normalPath[i + 1].index == spotIndex)
//					{
//						_normalPath.splice(i,1);
//					}
					nextSpotPos = seekAdjoinSpot(i,1);
					preSpotPos = seekAdjoinSpot(i,-1);
					return {pre:preSpotPos,next:nextSpotPos};
				}
			}
			return null;
		}
		
		private function seekAdjoinSpot(pos:int,dir:int):int
		{
			var posNow:int = pos + dir;
			if(_normalPath[posNow] == null) return -1;
			if(_normalPath[posNow].nodeType == nodeStruct.TYPE_SPOT)
			{
				return posNow;
			}else
			{
				return seekAdjoinSpot(posNow,dir);
			}
		}
		/**
		 *找寻两点间最小的路线 
		 */		
		public function startSeek(startIndex:String,endIndex:String):void
		{
			_shortPath.cost = 999;
			seekPath(seekNodeByIndex(startIndex),startIndex,endIndex);
		}
		
		private function seekPath(node:nodeStruct,startIndex:String,endIndex:String):void
		{
			if(!node) return;
			node.parentNodeIndex = startIndex;
			node.isLock = true;
			for(var i:int=0;i<node.linkNodeList.length;i++)
			{
				if(node.index == endIndex)
				{
					generatePath(node);//生成路线 并且继续遍历下个相连的结点
					trace("开始生成路线---------------------" + i);
					node.isLock = false;
					return;
				}
				else if(node.linkNodeList[i].index != startIndex)
				{
					var nodeTemp:nodeStruct = seekNodeByIndex(node.linkNodeList[i].index);
					if(!nodeTemp)
					{
						continue;
					}
					else if(nodeTemp.isLock == true)
					{
						continue;
					}else
					{
						seekPath(nodeTemp,node.index,endIndex);
					}
				}
			}
			node.isLock = false;
		}
		
		private function generatePath(node:nodeStruct):void
		{
			var pathList:Array = [];
			var tempNode:nodeStruct = node;
			var cost:uint = 0;
			while(tempNode.index != tempNode.parentNodeIndex)
			{
				pathList.unshift(tempNode);
				cost += uint(ArrayUtils.seekByIndex(tempNode.linkNodeList,tempNode.parentNodeIndex).cost);
				tempNode = seekNodeByIndex(tempNode.parentNodeIndex);
			}
			cost += uint(ArrayUtils.seekByIndex(tempNode.linkNodeList,tempNode.parentNodeIndex).cost);
			pathList.unshift(tempNode);
			if(_shortPath.cost > cost)
			{
				_shortPath.cost = cost;
				_shortPath.path = pathList;
			}
		}
		
		/**
		 * 根据id寻找_nodeList里记录的node信息
		 *
		 */		
		private function seekNodeByIndex(index:String):nodeStruct
		{
			for(var i:int=0;i<_nodeList.length;i++)
			{
				if(_nodeList[i].index == index)
				{
					return _nodeList[i];
				}
			}
			return null;
		}
		
		/**
		 *将xml路线数据 中的所有不同的结点提取出来  
		 * @param roadList
		 */		
		private function generateNodeIndexList(roadList:Array):void
		{
			var len:int = roadList.length;
			var tempNodePath:Object;
			var tempList:Array;
			for(var i:int=0;i<len;i++)
			{
				tempNodePath = roadList[i];
				tempList = tempNodePath.pathID.split("-");
				if(tempList.length != 2) continue;
				checkIsNewNode(tempList[0],tempList[1]);
			}
		}
		/**
		 * 判断传入的两个点是否是新的结点
		 */		
		private function checkIsNewNode(startIndex:String,endIndex:String):void
		{
			var isStartNew:Boolean = true;
			var isEndNew:Boolean = true;
			var len:int = _nodeIndexList.length;
			for(var i:int = 0;i<len;i++)
			{
				if(_nodeIndexList[i] == startIndex)
				{
					isStartNew = false;
				}else if(_nodeIndexList[i] == endIndex)
				{
					isEndNew = false;
				}
			}
			if(isStartNew)
			{
				_nodeIndexList.push(startIndex);
			}else if(isEndNew)
			{
				_nodeIndexList.push(endIndex);
			}
		}
		/**
		 *根据 _nodeIndexList数组里的所有不同结点，生成一个包含结点信息以及结点之间关系的数组
		 * 
		 */		
		private function generateNodeList():void
		{
			var len:int = _nodeIndexList.length;
			for(var i:int=0;i<len;i++)
			{
				var node:nodeStruct = seekNode(_nodeIndexList[i]);
				if(node != null)
				{
					_nodeList.push(node);
				}
			}
		}
		/**
		 * 遍历数组，将结点关系写入
		 */		
		private function seekNode(index:String):nodeStruct
		{
			var len:int = _roadInfoList.length;
			var pathNode:Object;
			var node:nodeStruct = new nodeStruct();
			node.index = index;
			var tempList:Array;
			for(var i:int=0;i<len;i++)
			{
				pathNode = _roadInfoList[i];
				tempList = pathNode.pathID.split("-");
				if(tempList.length != 2) continue;
				if(tempList[0] == index)
				{
					node.linkNodeList.push({index:tempList[1],cost:pathNode.time});
				}else if(tempList[1] == index)
				{
					node.linkNodeList.push({index:tempList[0],cost:pathNode.time});
				}
			}
			return node;
		}
		
		private function checkNodesNeedVisit(startIndex:String,endIndex:String):Boolean
		{
			if(endIndex == null) return false;
			var node:nodeStruct;
			var roadNum:int;
			for(var i:int=0;i<_normalPath.length;i++)
			{
				node = _normalPath[i];
				if(node.index == startIndex)
				{
					++ roadNum;
				}else if(node.index == endIndex)
				{
					if(roadNum < 2)
					{
						return false;
					}else
					{
						return true;
					}
				}
				if(roadNum > 0)
				{
					if(node.nodeType == nodeStruct.TYPE_ROAD || node.needVisit == false)
					{
						++ roadNum;
					}
				}
			}
			return false;
		}
		
		public function get addPath():Array
		{
			return _addPath;
		}
		
		public function get removePath():Array
		{
			return _removePath;
		}
		
		public function get normalPath():Array
		{
			return _normalPath;
		}
		
	}
}


class nodeStruct
{
	public var index:String;
	public var needVisit:Boolean = true;//标志该景点是否需要访问
	public var parentNodeIndex:String;//父节点id
	public var parentNodeCost:uint;//到父节点的代价
	public var isLock:Boolean;//标志寻路状态
	public var linkNodeList:Array = [];//相连的所有结点
	
	public static const TYPE_SPOT:int = 2;
	public static const TYPE_ROAD:int = 1;
	public function get nodeType():int
	{
		if(index.charCodeAt(0) > 57)
		{
			return TYPE_ROAD//为地点类型
		}else
		{
			return TYPE_SPOT//为景点类型
		}
	}
}
